#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//n是一共需要排列的数字
//P是用户输入的数组
//A是排列的数组
//cur是已经确定的数字个数

//输出1-n的全排列
void print_permutation(int n,int* A,int cur){
    //数字已全部确定，按顺序打印
    if(cur==n){
        for(int i=0;i<n;i++){
            printf("%d ",A[i]);
        }
        printf("\n");
    }
    else{
        //循环检查i
        for(int i=1;i<=n;i++){
            int ok=1;
            //检查在已确定的数字中是否有i
            for(int j=0;j<cur;j++){
                if(A[j]==i){
                    ok=0;
                }
            }
            //i未出现，添加到排列数组末尾，再次递归
            if(ok){
                A[cur]=i;
                print_permutation(n,A,cur+1);
            }
        }
    }
}
//输出1-n可重复元素的’全‘排列，免去了判断i是否已确定的步骤
void print_permutation_2(int n,int* A,int cur){
    //数字已全部确定，按顺序打印
    if(cur==n){
        for(int i=0;i<n;i++){
            printf("%d ",A[i]);
        }
        printf("\n");
    }
    else{
        for(int i=1;i<=n;i++){
            A[cur]=i;
            print_permutation_2(n,A,cur+1);
        }
    }
}
//输出所输入数组的全排列
void print_permutation_3(int n,int * P,int* A,int cur){
    if(cur==n){
        for(int i=0;i<n;i++){
            printf("%d ",A[i]);
        }
        printf("\n");
    }
    else{
        for(int i=0;i<n;i++){
            int c1=0,c2=0;
            if(!i || P[i]!=P[i-1]){
                for(int j=0;j<cur;j++){
                    if(A[j]==P[i]){
                        c1++;
                    }
                }
                for(int j=0;j<n;j++){
                    if(P[i]==P[j]){
                        c2++;
                    }
                }
                if(c1<c2){
                    A[cur]=P[i];
                    print_permutation_3(n,P,A,cur+1);
                }
            }
        }
    }
}
//输出所输入数组的可重复‘全’排列
void print_permutation_4(int n,int * P,int* A,int cur){
    if(cur==n){
        for(int i=0;i<n;i++){
            printf("%d ",A[i]);
        }
        printf("\n");
    }
    else{
        for(int i=0;i<n;i++){
            A[cur]=P[i];
            print_permutation_2(n,A,cur+1);
        }
    }
}
int main(void){
    int A[4]={0};
    int P[4]={1,3,5,2};
    print_permutation_4(4,P,A,0);
    return 0;
}